package xio.leetcode.java;

import xio.leetcode.java.base.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 144. Binary Tree Preorder Traversal (Medium)
 * 给定一个二叉树，返回它的 前序 遍历。
 *
 *  示例:
 *
 * 输入: [1,2,3,null,null,4,5]
 *    1
 *  /  \
 * 2    3
 *     / \
 *    4  5
 *
 * 输出: [1,2,3,4,5]
 * 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
 *
 * 我们使用两种解法来完成
 */
public class LC144_PreorderTraversal {

    List<Integer> result= new ArrayList<>();
    /**
     * 递归解法
     * 递归的解法很简单，就是先记录当前节点值，然后执行访问左右节点的递归方法即可。
     */
    public List<Integer> preorderTraversal(TreeNode root) {
        dfs(root);
        return result;
    }

    private void dfs(TreeNode node) {
        if (node == null) {
            return;
        }
        result.add(node.val);
        dfs(node.left);
        dfs(node.right);
    }

    /**
     * 迭代解法
     * 思路：使用栈来存储遍历的节点，因为是前序遍历，结合栈FILO的特点，我们每次把先让右节点入栈，
     * 左节点后入，那每次遍历首先访问到的就是左节点，即可完成前序遍历。
     */
    public List<Integer> preorderTraversal2(TreeNode root) {

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.empty()){
            TreeNode node = stack.pop();
            if (node == null){
                continue;
            }
            result.add(node.val);
            stack.push(node.right);
            stack.push(node.left);
        }
        return result;
    }


}
